package com.zhang.trie;


import com.zhang.map.HashMap;

/**
 * @author 张吉鑫
 * @Description 字典树
 * @date 2021/4/9 19:37
 */
public class Trie<V> {
    private Node<V> root;
    private int size;

    public Trie() {
    }

    /**
     * 元素数量
     * @return
     */
    public int size(){
        return size;
    }

    /**
     * 判断是否为空
     * @return
     */
    public boolean isEmpty(){
        return size == 0;
    }

    /**
     * 清空元素
     */
    public void clear(){
        size = 0;
        root = null;
    }

    /**
     * 通过键查找值
     * @param key
     * @return
     */
    public V get(String key){
        Node<V> node = node(key);
        return node != null && node.word ? node.value : null;
    }

    /**
     * 查看是否包含此元素
     * @param str
     * @return
     */
    public boolean contains(String str){
        Node<V> node = node(str);
        return node != null && node.word;
    }

    /**
     * 添加元素
     * @param str
     * @param value
     * @return
     */
    public V add(String str,V value){
        keyCheck(str);
        if (root == null){
            root = new Node<>(null);
        }
        Node<V> node = root;
        int len = str.length();
        for (int i = 0; i < len; i++) {
            char c = str.charAt(i);
            boolean b = node.children == null;
            Node<V> vNode = b ? null : node.children.get(c);
            if (vNode == null){
                vNode = new Node<>(node);
                node.children = b ? new HashMap<>() : node.children;
                node.children.put(c, vNode);
            }
            node = vNode;
        }
        if (node.word){
            V v = node.value;
            node.value = value;
            return v;
        }

        node.word = true;
        node.value = value;
        size++;
        return null;
    }

    /**
     * 删除元素
     * @param str
     * @return
     */
    public V remove(String str){
        Node<V> node = node(str);
        if (node == null || !node.word){
            return null;
        }
        V oldValue = node.value;
        size--;
        if (node.children != null && !node.children.isEmpty()){
            node.word = false;
            node.value = null;
            return oldValue;
        }


        int len = str.length();
        for (int i = len - 1; i >= 0; i--) {
            char c = str.charAt(i);
            Node<V> parent = node.parent;
            parent.children.remove(c);
            if (parent.word || !parent.children.isEmpty()){
                break;
            }
            node = parent;
        }

        return oldValue;
    }

    /**
     * 判断是否已元素开头
     * @param prefix
     * @return
     */
    public boolean startsWith(String prefix){
        keyCheck(prefix);
        return node(prefix) != null;
    }

    /**
     * 通过键获取节点
     * @param key
     * @return
     */
    private Node<V> node(String key){
        if (root == null){
            return null;
        }
        keyCheck(key);
        Node<V> node = this.root;
        int len = key.length();
        for (int i = 0; i < len; i++) {
            if (node == null || node.children == null || node.children.isEmpty()){
                return null;
            }
            char c = key.charAt(i);
            node = node.children.get(c);
        }
        return node;
    }

    /**
     * 检查键
     * @param key
     */
    private void keyCheck(String key){
        if (key == null || key.length() == 0){
            throw new IllegalArgumentException("key must not be empty");
        }
    }

    private static class Node<V> {
        Node<V> parent;
        HashMap<Character,Node<V>> children;
        V value;
        boolean word;

        public Node(Node<V> parent){
            this.parent = parent;
        }
    }
}
